package org.wyw.solution;

import org.wyw.entiry.ListNode;

@Solution(
        id = 1,
        title = "链表相交",
        difficulty = "medium",
        link = "https://leetcode.cn/problems/intersection-of-two-linked-lists/description/"
)
public class Solution009 {
    /**
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。(注意：链表相交不是交叉，相交后交点后面的节点都是相同的)
     * 题目数据 保证 整个链式结构中不存在环。
     *
     * 思路： 双指针
     * 两个指针分别遍历两个链表A和B， 遍历完各自的链表后在遍历对方的链表
     * 1.若相交，则会在交点相遇
     *      1. 若 A 长度等于B ,则会在遍历自己的链表的时候相遇
     *      2. 若 长度不等，则会在遍历对方的链表的时候相遇
     * 2.否则 不相交
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        ListNode a = headA,b = headB;
        //若相交则 在交点的时候跳出循环，若不相交，则都遍历完对方后，a=b=null 跳出循环
        while ( a != b){
            //自己的遍历完后遍历对方的链表
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }

}
